Background: Despite the recognition of stigma as a hindrance to public health treatment and prevention there are gaps in evidence on the relationship between HIV stigma and VCT services utilization in Nigeria. The purpose of this study was to examine a community’s perceptions, feelings and attitudes towards people living with HIV/AIDS and how this is associated with access to utilization of voluntary counselling and treatment in Nigeria. Methods: A cross-sectional random study of Nigerians, using a mixed-method approach was carried out in two distinct ethnic areas of the country. Both quantitative and qualitative methods (mixed-methods) were used to collect data in Osun State (Yoruba ethnic group) in the South-West and Imo State (Igbo ethnic group) in the South East. Multivariate logistic regression was the model used to examine the association of interest. Results: It is shown that Nigerian public attitudes to HIV/AIDS and those infected with the disease are negative. The markers for stigma on the overall stigma index are significant predictors of utilization of voluntary counselling and testing. As the sum of negative feelings increases, there is less likelihood to using voluntary counselling and testing (VCT) and vice versa. Conclusions: Current national efforts at addressing the AIDS pandemic can only be successful when the issue of AIDS is de-stigmatized and is made a critical part of those efforts. One way to do this is through well-designed messages that should be posted in the media, community halls, health centers and other public places aimed at humanizing the disease and those affected and infected by it.